package it.storm.solution;

/**
 * 1742. 盒子中小球的最大数量
 * https://leetcode-cn.com/problems/maximum-number-of-balls-in-a-box/
 */
public class Solutions_1742 {
    public static void main(String[] args) {
//        int lowLimit = 1, highLimit = 10;  // output: 2
//        int lowLimit = 5, highLimit = 15;  // output: 2
//        int lowLimit = 19, highLimit = 28;  // output: 2
        int lowLimit = 11, highLimit = 104;  // output: 9

        int result = countBalls(lowLimit, highLimit);
        System.out.println(result);
    }

    /**
     * 解法二：数学法（8ms）
     * 若有区间 [18, 28]
     * 可以利用 18 的位数和，计算出 19 的位数和，利用 19 的位数和，计算出 20 的位数和
     * 省去对每一位数都进行位数和计算的操作
     *
     * 像 18 到 19 的，位数和从 9 到 10，即加了个 1
     * 但是 19 到 20，位数和却是从 10 到了 2，其中反而减少了 8
     *     199 到 200，位数和却是从 19 到了 2，其中反而减少了 17
     *     1999 到 2000，位数和却是从 28 到了 2，其中反而减少了 26
     *
     * 规律：若 i 数字的后面有 n 个 0，则比前一数字的位数和减少了：1 - n * 9
     *      否则比前一数字的位数和多 1
     */
    public static int countBalls(int lowLimit, int highLimit) {
        int[] counts = new int[46];
        int res = 1;
        int idx = 0;
        // 计算出 lowLimit 的位数和
        for (int i = lowLimit; i > 0; i /= 10) {
            idx += i % 10;
        }
        counts[idx] ++;
        // 根据前一位数，
        for (int i = lowLimit + 1; i <= highLimit; i++) {
            // 判断数字 i 末尾有多少位 0
            int j = getNumLastZero(i);
            idx = idx + 1 - j * 9;
            // 边记录，边比较
            res = Math.max(res, ++ counts[idx]);
        }
        return res;
    }

    public static int getNumLastZero(int num) {
        int res = 0;
        while (num % 10 == 0) {
            num /= 10;
            res ++;
        }
        return res;
    }

    /**
     * 解法一：暴力法（24ms）
     */
    public static int countBalls2(int lowLimit, int highLimit) {
        int res = 0;
        // highLimit 最大表示 99999
        // counts[10] = 9，表示 [lowLimit, highLimit] 中，各位数相加等于 9 的数字有 9 个
        int[] counts = new int[46];
        for (int i = lowLimit; i <= highLimit; i++) {
            int temp = i;
            int j = 0;
            while (temp > 0) {
                j += temp % 10;
                temp /= 10;
            }
            // 各位数的和为 j
            // 记录位数和同时比较最大值
            res = Math.max(res, ++ counts[j]);
        }
        return res;
    }
}
